package 中等.其他;

import java.util.Arrays;
import java.util.Random;

/**
 * 给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。
 * <p>
 * 实现 Solution class:
 * <p>
 * Solution(int[] nums) 使用整数数组 nums 初始化对象
 * int[] reset() 重设数组到它的初始状态并返回
 * int[] shuffle() 返回数组随机打乱后的结果
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/shuffle-an-array
 */
public class 打乱数组_384 {

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        Solution solution = new Solution(nums);
        System.out.println(Arrays.toString(solution.shuffle()));
        System.out.println(Arrays.toString(solution.reset()));
    }


    public static class Solution {

        private int[] oldNums;

        private int[] newNums;

        /**
         * 原地洗牌算法
         * 直接在原始数组上面操作，假设数组长度为n
         * 首先在[0,n-1]中取一个随机数，和数组有序部分的最后一个元素进行交换，
         * 那么，[0,n-2]是有序部分，[n-1,n-1]是无序部分，
         * 然后在有序部分[0,n-2]随机取一个数，和最后一个元素进行交换
         * 那么，有序部分[0,n-3]，无序部分[n-2,n-1]
         * 以此类推...
         *
         * @param nums
         */
        public Solution(int[] nums) {
            if (nums != null) {
                oldNums = nums;
                newNums = new int[oldNums.length];
                //使用本地方法，复制数组效率最高
                System.arraycopy(oldNums, 0, newNums, 0, oldNums.length);
            }
        }

        public int[] reset() {
            return oldNums;
        }

        public int[] shuffle() {
            if (newNums != null) {
                Random random = new Random();
                for (int i = newNums.length - 1; i > 0; i--) {
                    //随机数取值范围[0,i+1-1]=[0,i]
                    replace(random.nextInt(i + 1), i);
                }
            }
            return newNums;
        }

        public void replace(int resource, int target) {
            int targetNum = newNums[target];
            newNums[target] = newNums[resource];
            newNums[resource] = targetNum;
        }
    }

}
